#pragma once
#include <vector>

using namespace std;

enum class EHeapType
{
	MinHeap,
	MaxHeap
};

template<typename Unique,typename Comparable>
struct DataBase
{
	DataBase()
	{

	}

	DataBase( Unique _key, Comparable _data ) : Key( _key ), Data( _data )
	{

	}

	bool operator > ( const DataBase<Unique, Comparable>& rhs )
	{
		return this->Data > rhs.Data;
	}

	bool operator < ( const DataBase<Unique, Comparable>& rhs )
	{
		return this->Data < rhs.Data;
	}

	Unique Key;
	Comparable Data;
};

template<typename Unique, typename Comparable>
class PriorityQueue
{

public:
	
	PriorityQueue()
	{

	}

	PriorityQueue( EHeapType _heapType): HeapType(_heapType)
	{
		
	}

	~PriorityQueue()
	{

	}

	void Print(string TextBeforePrint = "")
	{
		if(Heap.size() == 0)
			return;

		cout << "\n\n";

		cout << TextBeforePrint << "\t";
		for (int i = 0; i < Heap.size(); i++)
		{
			string SplitText = i == Heap.size() - 1 ? "" : "  |  ";
			cout << "{" << Heap[i].Key << "," << Heap[i].Data << "}" << SplitText;
		}
		cout << "\n\n";
	}

	DataBase<Unique, Comparable> Top() const
	{
		return Heap[0];
	}

	bool Empty() const
	{
		return Heap.size() == 0;
	}

	int Size() const
	{
		return Heap.size();
	}

	int FindIndexByKey(Unique Key) const
	{
		for (int i = 0; i < Heap.size(); i++)
		{
			if (Key == Heap[i].Key)
			{
				return i;
			}
		}

		return -1;
	}

	void Insert( DataBase<Unique, Comparable> _value )
	{
		Heap.push_back(_value);
		Float(Heap.size() - 1);
	}

	void Pop()
	{
		if(Heap.size() <= 0)
			return;

		Heap[0] = Heap[Heap.size() - 1];
		Heap.pop_back();

		Sink(0);
	}

	void BuildHeap(const vector< DataBase<Unique, Comparable> >& _array )
	{
		for (int i = 0; i < _array.size(); i++)
		{
			DataBase<Unique,Comparable> temp = _array[i];

			Insert( temp );
		}

	}

	//remove by key value and keep data priority queue
	void Remove( Unique Key )
	{
		int KeyIndex = FindIndexByKey(Key);
		
		if(KeyIndex == -1)
			return;

		Heap[KeyIndex] = Heap[Heap.size() - 1];
		Heap.pop_back();

		Sink(KeyIndex);
	}

	bool ModifyData( Unique Key, Comparable NewValue )
	{
		int KeyIndex = FindIndexByKey(Key);

		if(KeyIndex == -1)
			return false;

		Heap[KeyIndex].Data = NewValue;

		//try filter up
		Float(KeyIndex);

		return true;
	}

	void Float( int StartIndex )
	{
		if(StartIndex <= 0 || Heap.size() <= 1)
			return;

		int CurrentIndex = StartIndex;
		//one node two child
		int ParentIndex = (CurrentIndex - 1) / 2;

		DataBase<Unique,Comparable> Temp = Heap[CurrentIndex];

		//Stop only when reach root
		while (CurrentIndex > 0)
		{
			if (ShouldLeftSwapWithRight(Heap[ParentIndex],Temp))
			{
				break;
			}
			else
			{
				Heap[CurrentIndex] = Heap[ParentIndex];
				CurrentIndex = ParentIndex;
				ParentIndex = (CurrentIndex - 1) / 2;
			}
		}

		Heap[CurrentIndex] = Temp;
	}

	void Sink( int StartIndex)
	{
		if(Heap.size() <= 1)
			return;

		int CurrentIndex = StartIndex;
		int LeftNodeIndex = CurrentIndex * 2 + 1;
		DataBase<Unique, Comparable> Temp = Heap[CurrentIndex];

		while (LeftNodeIndex < Heap.size())
		{
			if (LeftNodeIndex + 1 < Heap.size())
			{
				//Should Swap When should float,in this case is sink so using NOT swap
				bool bSwap = !ShouldLeftSwapWithRight( Heap[LeftNodeIndex], Heap[LeftNodeIndex + 1] );
				if (bSwap)
					LeftNodeIndex++;
			}

			//Stop When Should Float
			if (ShouldLeftSwapWithRight( Temp, Heap[LeftNodeIndex] ))
				break;
			else
			{
				Heap[CurrentIndex] = Heap[LeftNodeIndex];

				CurrentIndex = LeftNodeIndex;
				LeftNodeIndex = CurrentIndex * 2 + 1;
			}
		}

		Heap[CurrentIndex] = Temp;
	}

	bool ShouldLeftSwapWithRight( const DataBase<Unique,Comparable>& Left, const DataBase<Unique,Comparable>& Right )
	{
		if (HeapType == EHeapType::MinHeap)
		{
			return Left.Data < Right.Data;
		}
		else if(HeapType == EHeapType::MaxHeap)
		{
			return Left.Data >= Right.Data;
		}
	}

protected:

	//binary heap
	vector< DataBase<Unique, Comparable> > Heap;

	EHeapType HeapType = EHeapType::MaxHeap;
};

template<typename Unique, typename Comparable>
void MergeTwoPriorityQueue( PriorityQueue<Unique, Comparable>& _QueueA, PriorityQueue<Unique, Comparable>& _QueueB )
{
	if (_QueueA.Size() < _QueueB.Size())
	{
		cout << "Queue B size is bigger than Queue A, Final Priority Heap Type Follow Queue B" << endl;
		swap( _QueueA, _QueueB );
	}
	else
	{
		cout << "Final Priority Heap Type Follow Queue A" << endl;
	}

	while (!_QueueB.Empty())
	{
		_QueueA.Insert( _QueueB.Top() );
		_QueueB.Pop();
	}
}
